\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Antibes}
  \setbeamercovered{transparent}
}

\usepackage{hyperref}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[portuguese]{babel}
\usepackage[utf8]{inputenc}
\usepackage{multirow}
\usepackage{times}

\title[Trabalho 3]
{Trabalho 3}

\subtitle
{Um algoritmo distribuído para encontrar aleatoriamente um conjunto de palavras}

\author
{Filipe~Neto \and Rommel~Cruz \and Samuel~Fadel}

\institute[Universidade de São Paulo]
{
  Instituto de Ciências Matemáticas e de Computação\\
  Universidade de São Paulo
}

\date[2013]
{SSC0143 -- Programação Concorrente, 2013}

\subject{Trabalho 3}

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}

%\AtBeginSection[]
%{
%  \begin{frame}<beamer>{Tópicos}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}


\begin{document}

\maketitle

\section{Objetivos}
\begin{frame}{Objetivos}
  Desenvolver um algoritmo paralelo, usando OpenMP~\cite{OpenMP} e
  MPI~\cite{MPI}, capaz de gerar, aleatoriamente um conjunto de palavras pré-definidas.
\end{frame}

\section{Requerimentos}
\begin{frame}{Requerimentos}
  \begin{itemize}
    \item Cada caractere de cada palavra foi gerado de forma totalmente
        aleatória
    \item Palavras com caracteres não alfabéticos foram descartadas
    \item Palavras com mais de cinco caracteres foram divididas em partes de, no
        máximo, cinco caracteres
    \item Portanto, foram geradas palavras com, no máximo, cinco caracteres
    \item Gerada uma palavra ou uma parte de palavra válida, esta foi
        marcada como encontrada e não foi aceita novamente
    \item Quando um processo encontrava uma palavra ou parte de palavra, os
        demais processos eram comunicados
    \item Foram calculados os tempos para encontrar 10\%, 20\%, 30\%, 40\%,
        50\%, 60\%, 70\%, 80\%, 90\% e 100\% do total de palavras
  \end{itemize}
\end{frame}

\section{Decomposição}
\begin{frame}{Decomposição do problema}
  \begin{itemize}
    \item Buscou-se minimizar a comunicação entre os processos, para que este não se tornasse o gargalo da solução.
    \item Foi construída uma árvore AVL para armazenar quais palavras estão sendo buscadas.
    \item Cada processo gera aleatoriamente uma palavra de até 5 letras e então buscá-la
na árvore.
	\item Não há necessidade de coordenar esta divisão entre vários processos.
	\item Para informar aos outros processos que uma palavra foi encontrada, um processo envia a todos os outros um número, que representa um nó da árvore.
  \end{itemize}
\end{frame}

\section{Solução}
\begin{frame}{Estruturas de Dados}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/dictionary.pdf}
  \end{figure}
\end{frame}

\begin{frame}{Decomposição do problema}
  \begin{itemize}
    \item A estrutura anterior, porém, não é suficiente para determinar a porcentagem de
palavras que já foram encontradas.
    \item Para isso, um nó é designado para ser o \emph{root} e nele é usada uma outra estrutura.
    \item Nesta outra estrutura, há a associação entre as palavras originais e suas partes
espalhadas pela árvore.
	\item No vetor, é armazenada a quantidade de nós que compõem a palavra.
  \end{itemize}
\end{frame}

\begin{frame}{Estruturas de Dados}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.8\linewidth]{img/rdictionary.pdf}
  \end{figure}
\end{frame}

\section{Implementaç\~ao}
\begin{frame}{Detalhes de Implementaç\~ao}
\begin{itemize}
\item Garantiu-se que cada thread responsável pela geração de palavras
tivesse uma raiz aleatória diferente, reduzindo o número de palavras geradas repetidamente
\item Destaca-se o uso de árvores AVL com os nós indexados porque reduziu drasticamente o overhead de comunicação entre os processos
\item O implementação de uma thread exclusiva para o recebimento das palavras
encontradas por outros processos manteve todos os processos sincronizados
\item A limitação da Open MPI de não permitir envio e recebimento simultâneos de mensagens geraram um problema na coordenação, esse problema foi tratado utilizando a diretiva de trecho de código crítico da OpenMP
\end{itemize}
\end{frame}

\section{Resultados}
\subsection{Testes no Cluster}
\begin{frame}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.9\linewidth]{img/tempos.pdf}
  \end{figure}
\end{frame}

\begin{frame}
  \begin{figure}[h]
    \centering
    \includegraphics[width=0.9\linewidth]{img/tempos_leitura.pdf}
  \end{figure}
\end{frame}

\section{Conclusões}
\begin{frame}{Conclusões}
  \begin{itemize}
    \item A solução proposta é altamente paralelizável
    \item Busca de palavras teve tempo reduzido pelo uso de mais processos
    \item Tempo de execução afetado apenas pela leitura do arquivo
  \end{itemize}
\end{frame}

\section*{Bibliografia e Referências}
\begin{frame}{Bibliografia e Referências}
  \begin{thebibliography}{9}
  \bibitem{OpenMP}
  OpenMP \\ \url{http://www.openmp.org/}
  \bibitem{MPI}
  MPI \\ \url{http://www.mcs.anl.gov/mpi/}
  \end{thebibliography}
\end{frame}

\end{document}
